class Solution
{
public:
    // 像是把两道题缝合起来了
    int maxPalindromes(string s, int k)
    {
        if (k == 1)
        {
            return s.size();
        }
        vector<vector<int>> palindromeAreas;
        int n = s.size();
        int halfK = k / 2;
        // 找到回文
        // 只需找到k或k+1长度即可
        for (int i = 0; i < n; ++i)
        {
            int oddHalf = halfK;
            if (i - oddHalf >= 0 && i + oddHalf < n)
            {
                bool oddPalindrome = true;
                for (int j = 1; j <= oddHalf; ++j)
                {
                    if (s[i - j] != s[i + j])
                    {
                        oddPalindrome = false;
                        break;
                    }
                }
                if (oddPalindrome)
                {
                    palindromeAreas.push_back({i - oddHalf, i + oddHalf});
                }
            }

            int evenHalf = halfK;
            if (k & 1)
            {
                ++evenHalf;
            }
            if (i - evenHalf + 1 >= 0 && i + evenHalf < n)
            {
                bool evenPalindrome = true;
                for (int j = 0; j < evenHalf; ++j)
                {
                    if (s[i - j] != s[i + 1 + j])
                    {
                        evenPalindrome = false;
                        break;
                    }
                }
                if (evenPalindrome)
                {
                    palindromeAreas.push_back({i - evenHalf + 1, i + evenHalf});
                }
            }
        }
        int palindromeCount = palindromeAreas.size();
        if (palindromeCount == 0)
        {
            return 0;
        }

        // 选出最多不重复的区间
        sort(palindromeAreas.begin(), palindromeAreas.end(), [](auto &v1, auto &v2)
             {
            if(v1[1] == v2[1])
            {
                return v1[0] > v2[0];
            }
            else
            {
                return v1[1] < v2[1];
            } });
        int count = 1;
        int end = palindromeAreas[0][1];
        for (int i = 1; i < palindromeCount; ++i)
        {
            if (palindromeAreas[i][0] > end)
            {
                ++count;
                end = palindromeAreas[i][1];
            }
        }
        return count;
    }
};